package leetcode_day._2022._202209._2130;

/**
 * 相似度为 K 的字符串
 * 算法：回溯
 *
 * @author yzh
 * @version 1.0
 * @date 2022/9/21 21:38
 */
public class _21_854 {

    int ans = Integer.MAX_VALUE;

    public int kSimilarity(String s1, String s2) {
        return dfs(s1.toCharArray(), s2.toCharArray(), 0, 0);
    }

    int dfs(char[] cs1, char[] cs2, int idx, int k) {
        // 如果当前交换次数已经超过最小交换次数, 终止递归
        if (k >= ans) return ans;
        // 如果遍历到头了, 表示 s1 和 s2 已经相等了, 终止递归
        if (idx == cs1.length) {
            ans = Math.min(ans, k);
            return k;
        }
        for (int i = 0; i < cs1.length; i++) {
            // 两个字符串在当前位置的字符不相等
            if (cs1[i] != cs2[i]) {
                // s2 从 i + 1 查找可以交换的字符
                for (int j = i + 1; j < cs2.length; j++) {
                    // 在 s2 的 i + 1 后面找到等于 s1[i] 的字符, 但这个字符不能与 s1[j] 相等
                    // 不能把原来就相等的字符打乱, 一次剪枝操作
                    if (cs2[j] == cs1[i] && cs2[j] != cs1[j]) {
                        swap(cs2, i, j);
                        dfs(cs1, cs2, idx + 1, k + 1);
                        swap(cs2, i, j);
                        // 如果 cs1 的 j 位与 cs2 的 i 位相等, 说明这是一次最佳交换, 直接结束
                        if (cs1[j] == cs2[i]) break;
                    }
                }
                // 当前位置的两个字符不相等, 不能继续往后比较了
                // 相当于跳出循环, 但不能 break, 如果 k 为 0, 这里 break 了, 就返回 0 了, 结果不对
                return ans;
            }
        }
        ans = Math.min(ans, k);
        return ans;
    }

    void swap(char[] cs, int i, int j) {
        char tmp = cs[i];
        cs[i] = cs[j];
        cs[j] = tmp;
    }

}
